package com.jiang.专题.哈希表.Q229;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/04/01 13:22
 */
public class Solution {
    // 哈希表
//    public List<Integer> majorityElement(int[] nums) {
//        Map<Integer, Integer> map = new HashMap<>();
//        List<Integer> res = new ArrayList<>();
//        int times = nums.length / 3;
//        if (times == 0) {
//            return Arrays.stream(nums).distinct().boxed().collect(Collectors.toList());
//        }
//        for (int num : nums) {
//            Integer v = map.get(num);
//            if (v != null) {
//                if (v == times) {
//                    res.add(num);
//                }
//                map.put(num, v + 1);
//            } else {
//                map.put(num, 1);
//            }
//        }
//        return res;
//    }

    // 摩尔投票法
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        int cand1 = nums[0], count1 = 0;
        int cand2 = nums[0], count2 = 0;

        for (int num : nums) {
            if (cand1 == num) {
                count1++;
                continue;
            }
            if (cand2 == num) {
                count2++;
                continue;
            }

            if (count1 == 0) {
                cand1 = num;
                count1++;
                continue;
            }

            if (count2 == 0) {
                cand2 = num;
                count2++;
                continue;
            }

            count1--;
            count2--;
        }

        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (cand1 == num) count1++;
            else if (cand2 == num) count2++;
        }

        if (count1 > nums.length / 3) res.add(cand1);
        if (count2 > nums.length / 3) res.add(cand2);

        return res;
    }
}
